package me.yobol.datastructure.basic.list.sequence;

import me.yobol.datastructure.basic.list.List;
import me.yobol.datastructure.basic.list.Node;

/**
 * 顺序表是线性表的顺序存储结构，即用一组地址连续的存储单元，依次存储数据表中的数据元素。
 * 要求逻辑上相邻的数据元素在物理位置上也相邻。
 * 因此在实际实现中常借助于数组实现。考虑到数组的特性——定长，不易拓展；可以随机存取。
 * 
 * 线性表中元素的位序是从1开始的，而数组中的元素下标是从0开始的。
 * 
 * 顺序表最主要的特点是随机访问，即通过首地址和元素序号可以在O(1)的时间内找到指定元素。
 * 顺序表的存储密度高，每个结点只存储数据元素，不包含指针域。
 * 
 * 在表尾插入/删除结点时，无需后移/前移元素，时间复杂度为0(1)
 * 在第i个位置插入/删除结点时，平均时间复杂度为O(n)[增n/2,删(n-1)/2]
 * 在表头插入/删除结点时，时间复杂度为O(n)
 * 
 * 在任意位置按位查找时，时间复杂度都为O(1)；当按关键字查找时，表头O(1),表尾O(n)，在第i个位置平均时间复杂度为O(n)[(n+1)/2]
 * 
 * @author Yobol
 */
public class SequenceList implements List {

    private Node list[];
    private int size;
    private int capacity;//线性表最大长度，支持动态扩展
    private int increase;//线性表每次动态扩展的长度
    //public static final int capacity = 10;//线性表最大长度，不支持扩展

    public SequenceList() {
    }

    /**
     *
     */
    @Override
    public void init() {
        //静态分配
        this.list = new Node[capacity];
        this.size = 0;
        this.capacity = 10;
        this.increase = 5;
    }

    /**
     *
     * @return @throws java.lang.Exception
     */
    @Override
    public boolean isEmpty() throws Exception {
        if (list == null) {
            throw new Exception("未初始化");
        }
        return (this.size == 0);
    }

    /**
     *
     * @return
     */
    @Override
    public boolean isFull() throws Exception {
        if (list == null) {
            throw new Exception("未初始化");
        }
        return (this.size == capacity);
    }

    /**
     *
     * @return @throws Exception
     */
    @Override
    public int size() throws Exception {
        if (list == null) {
            throw new Exception("未初始化");
        }
        return this.size;
    }

    /**
     * 在指定位置插入节点(1 <= index <= capacity+1)
     *
     * @param index 对用户而言，index从1开始
     * @param node
     * @throws Exception
     */
    @Override
    public void insert(int index, Node node) throws Exception {
        if (list == null) {
            throw new Exception("未初始化");
        }
        if (isFull()) {//size >= capacity
            System.out.println("线性表长度加" + increase);
            capacity += increase;//支持动态扩展
            Node[] nList = new Node[capacity];
            for (int i = 0; i < size; i++) {
                nList[i] = list[i];
            }
            list = nList;
            //throw new Exception("线性表已满");//不支持动态扩展
        }
        if (index < 1 || index > size + 1) {
            throw new Exception("下标越界");
        }
        
        for (int i = size; i >= index; i--) {
                list[i] = list[i - 1];
        }
        list[index - 1] = node;
        size++;
    }
    
    /**
     * 在线性表表尾插入，时间复杂度为O(1)
     * 
     * @param node
     * @throws Exception 
     */
    @Override
    public void insert(Node node) throws Exception {
        insert(size+1,node);
    }

    /**
     * 删除指定位置的节点(1 <= index <= capacity )
     * 
     * 
     * 
     * @param index
     * @return
     * @throws Exception 
     */
    @Override
    public Node delete(int index) throws Exception {
        //int idx = index - 1;
        if (list == null) {
            throw new Exception("未初始化");
        }
        if (isEmpty()) {
            throw new Exception("线性表为空");
        }
        if (index < 1 || index > size) {
            throw new Exception("下标越界");
        }
        Node target = getByLocale(index);
        for (int i = index;i < size;i++){
            list[i-1] = list[i];
        }
        size--;
        return target;
    }

    @Override
    public Node getByLocale(int index) throws Exception {
        if (list == null) {
            throw new Exception("未初始化");
        }
        if (index < 1 || index > size) {
            throw new Exception("下标越界");
        }
        return list[index-1];
    }

    @Override
    public Node getByKey(int key) throws Exception {
        if (list == null) {
            throw new Exception("未初始化");
        }
        Node target = null;
        for (int i = 0; i < size; i++) {
            if (list[i].getKey() == key) {
                target = list[i];
                break;
            }
        }
        return target;
    }

    @Override
    public void print() throws Exception {
        if (list == null) {
            throw new Exception("未初始化");
        }
        System.out.println("--------------------------------");
        System.out.println("size : " + size);
        System.out.println("--------------------------------");
        for (int i = 0; i < size; i++) {
            System.out.println(i + 1 + " : " + list[i].getKey());
        }
    }
    
    /**
     * 
     * @throws Exception 
     */
    @Override
    public void clear() throws Exception {
        if (list == null) {
            throw new Exception("未初始化");
        }
        for (int i = 0; i < size; i++) {
            list[i] = null;
        }
        size = 0;
    }

    @Override
    public void destroy() throws Exception {
        if (list == null) {
            throw new Exception("未初始化");
        }
        list = null;
    }

    public int getCapacity() throws Exception {
        return capacity;
    }

    public int getIncrease() {
        return increase;
    }

    public void setIncrease(int increase) {
        this.increase = increase;
    }

}
